package algorithm.dynamic_programming;

import java.util.HashMap;

public class CoinsWay {

    public static int ways1(int[] arr, int aim){
        if(arr == null || arr.length == 0){
            return 0;
        }
        return process(arr, aim, 0);
    }

    public static int process(int[] arr, int rest, int index){
        if(index == arr.length)
            return rest == 0? 1 : 0;
        int res = 0;
        for (int num = 0; rest >= arr[index] * num ; num++) {
            res += process(arr, rest - arr[index] * num, index + 1);
        }
        return res;
    }

    public static int ways2(int[] arr, int aim){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        for (int i = 0; i < arr.length + 1; i++) {
            for (int j = 0; j < aim + 1; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(arr, aim, 0, dp);
    }

    public static int process2(int[] arr, int rest, int index, int[][] dp){
        if(index == arr.length){
            dp[index][rest] = rest == 0? 1 : 0;
            return dp[index][rest];
        }
        if(dp[index][rest] != -1){
            return dp[index][rest];
        }
        int res = 0;
        for (int num = 0; rest >= arr[index] * num ; num++) {
            res += process2(arr, rest - arr[index] * num, index + 1, dp);
        }
        dp[index][rest] = res;
        return dp[index][rest];
    }

    public static int ways3(int[] arr, int aim){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        int N = arr.length;
        dp[N][0] = 1;
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 0; j < aim + 1; j++) {
                int res = 0;
                for (int num = 0; j >= arr[i] * num ; num++) {
                    res += dp[i + 1][j - arr[i] * num];
                }
                dp[i][j] = res;
            }
        }
        return dp[0][aim];
    }

    public static int ways4(int[] arr, int aim){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        int N = arr.length;
        dp[N][0] = 1;
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 0; j < aim + 1; j++) {
                int res = dp[i + 1][j];
                if(j >= arr[i])
                    res += dp[i][j - arr[i]];
                dp[i][j] = res;
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {
        int[] arr = { 5, 10,50,100 };
        int sum = 1000;
        int i = ways1(arr, sum);
        int j = ways4(arr, sum);
        System.out.println(i);
        System.out.println(j);
    }
}
